package top.fengleifeng.question;

/**
 * @program: leetcode-test
 * @description:
 *
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
 *
 * 示例 1:
 *
 * 输入: [2,3,2]
 * 输出: 3
 * 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
 * 示例 2:
 *
 * 输入: [1,2,3,1]
 * 输出: 4
 * 解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
 *      偷窃到的最高金额 = 1 + 3 = 4 。
 * 通过次数57,316提交次数145,373
 * 在真实的面试中遇到过这道题？
 *
 * 是
 *
 * 否
 * 贡献者
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/house-robber-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: fengleifeng
 * @create: 2020-09-22 20:09
 **/
public class Num213打家劫舍II {
    // 第一个 长度   第二个 0代表没有选择这一位，1代表选择这一位的最大值     第三个代表选择了第一个没有   0表示没有选择，1表示选择了
    class Solution {
        public int rob(int[] nums) {
            int numsLength = nums.length;
            if(numsLength<=0){
                return 0;
            }
            int[][][] dps = new int[numsLength][2][2];
            dps[0][0][0] = 0;
            dps[0][0][1] = Integer.MIN_VALUE;
            dps[0][1][0] =  Integer.MIN_VALUE;
            dps[0][1][1] = nums[0];
            int result =  0;
            for (int i = 1; i < numsLength; i++) {
                if(i == numsLength-1){
                    dps[i][0][0] =  Math.max(dps[i - 1][0][0], dps[i - 1][1][0]);
                    dps[i][1][0] = Math.max(dps[i - 1][0][0] + nums[i], dps[i - 1][1][0]);
                    dps[i][0][1] =  Math.max(dps[i - 1][0][1], dps[i - 1][1][1]);
                    dps[i][1][1] = Math.max(dps[i - 1][0][1], dps[i - 1][1][1]);
                }else{
                    dps[i][0][0] =  Math.max(dps[i - 1][0][0], dps[i - 1][1][0]);
                    dps[i][1][0] = Math.max(dps[i - 1][0][0] + nums[i], dps[i - 1][1][0]);
                    dps[i][0][1] =  Math.max(dps[i - 1][0][1], dps[i - 1][1][1]);
                    dps[i][1][1] = Math.max(dps[i - 1][0][1] + nums[i], dps[i - 1][1][1]);
                }
            }
            int one =  Math.max(dps[numsLength - 1][0][0], dps[numsLength - 1][1][0]);
            int two =  Math.max(dps[numsLength - 1][0][1], dps[numsLength - 1][1][1]);
            return Math.max(one,two);
        }
    }

    public static void main(String[] args) {
        int[] ints = {1,2,3,1};
        int rob = new Num213打家劫舍II().new Solution().rob(ints);
        System.out.println(rob);
    }
}
